iT邦幫忙

2024 iThome 鐵人賽

DAY 23
0

hackMD原稿

以前在參加圍棋比賽的時候,我都會特地準備開局,就是對我想下出的開局做研究,然後將其記熟,比賽時在開局階段就不必花費太多時間思考,基本上所有棋手都會先研究開局,畢竟比賽會有時間限制,而開局階段是最能夠提前研究的階段,大多數棋手都會盡量節省開局的用時,將時間與精力投入到中後半盤。
不只是圍棋,西洋棋跟象棋也有很多知名開局,圍棋的話除了開局還有定石,就是局部雙方都可以滿意的下法,人類可以提前將開局的研究結果記起來,那電腦為什麼不行呢?
昨天提到了利用Transposition Table來儲存過往盤面資訊,那同理我們也可以先儲存開局啊,把計算好的開局先儲存起來,只要遇到相同盤面就只要查表就好了,這也是一種可以大幅提升程式棋力的優化方式。

Opening Book

Opening Book (開局庫)就是用來儲存開局的,而開局庫的好處除了讓程式在開局時的速度提升之外,還有另外兩大優點:

  1. 避免重複錯誤:如果你的程式會在某個情況下犯錯,那它再次遇到一樣有機會犯錯,如果這個錯誤是發生在開局時,那使用開局庫就是一種很簡單有效的優化方式。
  2. 多樣化開局:開局庫能夠提供多種開局選擇,讓程式不會總是選擇相同的開局,就算你在MCTS中有加上更多的隨機性,但它的選點始終有限,像是目前的圍棋AI的實力都已經遠超人類,那加入開局庫不是為了讓AI棋力變得更強,而是為了貼近人類的需求,讓AI能下出類似指導棋效果的開局,這樣才有教學意義。
    (像是黑嘉嘉圍棋教室中提供多種不同風格的AI,歡迎大家去體驗看看,再次偷偷置入XDD)

建立開局庫的方式

建立開局庫的方式主要分成兩種:

  • 被動式建構
    可以利用人類高手經過長時間研究累積下來的經驗法則,比如西洋棋開局庫,或是直接蒐集大量高手棋譜,對其進行分析與統計,比如之前很有名的圍棋網站奇譜士。
  • 主動式建構
    直接用搜索的方式來計算盤面,可以是Minimax、MCTS等各種方式,沒錯連Minimax都可以(當然你得搭配很多剪枝的方式),因為這次沒有什麼時間限制,你可以將深度設得非常深,花個一星期甚至一個月去建構開局庫,比如AlphaGo開局庫

儲存與使用方式

儲存的資訊通常包含盤面資訊、勝率或評分、可能的下一手、搜索次數等,總之就是看你的需求決定要存下哪些資訊。
使用的話當然不可能將盤面一一做比對,如果你費時一個月建出了一個超大型開局庫,有10萬個盤面,每下一手就要去搜索這個龐大開局庫,那用時可能還比沒有開局庫來得更長......
可以跟昨天一樣使用hash,程式載入開局庫就建一個hash map,遇到一個新盤面就去查詢,還可以用樹狀結構表示,節點為盤面,邊為可能的走法,從根節點開始比對,一路沿著分支走下去,離開開局庫時稱為脫譜(drop out of book)

其他開局庫

有時候我們不是從初始狀態開始設計開局庫的,也可能是局部的固定變化,例如圍棋定石庫(Joseki Book),如下圖是一個19x19圍棋盤的右下角。

image

要考慮到鏡像對稱、旋轉、黑白(先後手)交換等16種看似不同但其實相同的盤面,以下四個角落要視為同一種定石,其實一般開局庫也需要考慮這些,只是在定石上比較明顯就是了。

圍棋

教學開局庫

2017年12月11日AlphaGo開局庫正式上線。
根據黃士傑學長臉書的資訊,這個開局庫收集了23萬個人類的棋譜,收錄了約6000個近代圍棋史上主要的開局變化,每一個開局變化都固定延伸20步棋,每個下法都經過1000萬次的模擬,整個教學工具約有2萬個分支變化、37萬個盤面。

雖然現在應該沒有人會使用這個開局庫來練習了,但在當時這絕對是變化最多最強大的圍棋開局庫,Deepmind團隊並沒有只是設計出AlphaGo把人類電爆後就結束了,而是利用他們龐大的資源創建了這個開局庫讓人類學習,感恩Deepmind讚嘆Deepmind。

Reference


上一篇
Day22 Transposition Table
下一篇
Day24 Endgame Database
系列文
猴子也能懂的電腦對局 : 30天打造自己的對局AI30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言